Search for: All records

The paper studies the application of first-order methods to the problem of computing equilibria of large-scale extensive-form games. It introduces a new weighted entropy-based distance-generating function for instantiating first-order methods. The new function achieves significantly better strong-convexity properties than existing weight schemes for the dilated entropy while maintaining the same easily implemented closed-form proximal mapping as the prior state of the art. The paper then generalizes our new entropy distance function, as well as the whole class of dilated distance functions, to the scaled extension operator. This yields the first efficiently computable distance-generating function for the decision polytopes capturing correlated and team solution concepts for extensive-form games. By instantiating first-order methods with these regularizers, several new results are achieved, such as the first method for computing ex ante correlated team equilibria with a guaranteed 1/T rate of convergence and efficient proximal updates. 

Tâtonnement is a simple, intuitive market process where prices are iteratively adjusted based on the difference between demand and supply. Many variants under different market assumptions have been studied and shown to converge to a market equilibrium, in some cases at a fast rate. However, the classical case of linear Fisher markets have long eluded the analyses, and it remains unclear whether tâtonnement converges in this case. We show that, for a sufficiently small stepsize, the prices given by the tâtonnement process are guaranteed to converge to equilibrium prices, up to a small approximation radius that depends on the stepsize. To achieve this, we consider the dual Eisenberg-Gale convex program in the price space, view tâtonnement as subgradient descent on this convex program, and utilize novel last-iterate convergence results for subgradient descent under error bound conditions. In doing so, we show that the convex program satisfies a particular error bound condition, the quadratic growth condition, and that the price sequence generated by tâtonnement is bounded above and away from zero. We also show that a similar convergence result holds for tâtonnement in quasi-linear Fisher markets. Numerical experiments are conducted to demonstrate that the theoretical linear convergence aligns with empirical observations. 

Budget constraints are ubiquitous in online advertisement auctions. To manage these constraints and smooth out the expenditure across auctions, the bidders (or the platform on behalf of them) often employ pacing: each bidder is assigned a pacing multiplier between zero and one, and her bid on each item is multiplicatively scaled down by the pacing multiplier. This naturally gives rise to a game in which each bidder strategically selects a multiplier. The appropriate notion of equilibrium in this game is known as a pacing equilibrium. In this work, we show that the problem of finding an approximate pacing equilibrium is PPAD-complete for second-price auctions. This resolves an open question of Conitzer et al. [Conitzer V, Kroer C, Sodomka E, Stier-Moses NE (2022a) Multiplicative pacing equilibria in auction markets. Oper. Res. 70(2):963–989]. As a consequence of our hardness result, we show that the tâtonnement-style budget-management dynamics introduced by Borgs et al. [Borgs C, Chayes J, Immorlica N, Jain K, Etesami O, Mahdian M (2007) Dynamics of bid optimization in online advertisement auctions. Proc. 16th Internat. Conf. World Wide Web (ACM, New York), 531–540] are unlikely to converge efficiently for repeated second-price auctions. This disproves a conjecture by Borgs et al. [Borgs C, Chayes J, Immorlica N, Jain K, Etesami O, Mahdian M (2007) Dynamics of bid optimization in online advertisement auctions. Proc. 16th Internat. Conf. World Wide Web (ACM, New York), 531–540], under the assumption that the complexity class PPAD is not equal to P. Our hardness result also implies the existence of a refinement of supply-aware market equilibria which is hard to compute with simple linear utilities. Funding: This work was supported by National Science Foundation (CCF-1703925, IIS-1838154).